/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    vector<ListNode*> lists;

    // 时间复杂度为 O(kn * log k)
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        this->lists = lists;

        if (lists.size() == 0) {
            return nullptr;
        }

        return mergeLists(0, lists.size() - 1);
    }

    ListNode* mergeLists(int l, int r) {
        if (l == r) {
            return lists[l];
        }

        // 分治，先合并左边的所有链表，再合并右边的所有链表，然后再合并这两个链表
        ListNode *ll = mergeLists(l, (r + l) / 2);
        ListNode *lr = mergeLists((r + l) / 2 + 1, r);

        return merge(ll, lr);
    }

    // 合并两个链表
    ListNode* merge(ListNode *ll, ListNode *lr) {
        ListNode *prehead = new ListNode();
        ListNode *head = prehead;

        while (ll != nullptr && lr != nullptr) {
            if (ll->val <= lr->val) {
                head->next = ll;
                ll = ll->next;
            } else {
                head->next = lr;
                lr = lr->next;
            }

            head = head->next;
        }

        if (ll != nullptr) {
            head->next = ll;
        } else if (lr != nullptr) {
            head->next = lr;
        }

        return prehead->next;
    }
};

int main() {
    vector<vector<int>> nums = {{1,4,5},{1,3,4},{2,6}};
    vector<ListNode*> lists(nums.size());

    for (int i = 0; i < nums.size(); i++) {
        if (nums[i].size() == 0) {
            continue;
        }
        ListNode *head = lists[i] = new ListNode(nums[i][0]);
        for (int j = 1; j < nums[i].size(); j++) {
            head->next = new ListNode(nums[i][j]);
            head = head->next;
        }
    }

    ListNode *l3 = Solution().mergeKLists(lists);

    cout << '[';

    while (l3 != nullptr) {
        if (l3->next != nullptr) {
        cout << l3->val << ", ";
        } else {
        cout << l3->val;
        }
        l3 = l3->next;
    }

    cout << ']' << endl;

    return 0;
}